#include <iostream>
#include <fstream>
#include <iomanip>
#include <algorithm>

using namespace std; 

// Carraghan Pardalos algorithm           //
// Bogdan coloring pointer implementation //
// Sandor Szabo Pecs 2012 11 10           //
 

fstream file1, file2, file3;
           
//-----------------------------------//
// routines for the incidence matrix //
//-----------------------------------//

void displayinc()
{ // Displays the incidence matrix. //
  // The size is gsize by gsize.    //
  int i,j,x;

  cout << "The incidence matrix." << endl;
  if ( displ==1 )
  { for (i=1; i<=gsize; i++)
    { cout << endl;
      for (j=1; j<=gsize; j++)
      { cout << inc[i][j]; }
    }
  }
  esize=0;
  for (i=1; i<=gsize-1; i++)
  { for (j=i+1; j<=gsize; j++)
    { if ( inc[i][j] ) { esize++; } }
  } 
  cout << endl;
  cout << "gsize=" << gsize << endl;
  cout << "esize=" << esize << endl;
  cout << "Press 9 to continue" << endl;
  //cin >> x;     
} 

void readinc(string in_file_name) 
{ // Reads the incidence matrix from the disc. //
  int i,j,x;
   
  file1.open(in_file_name.c_str(), ios::in); 
  i=1; j=1;
  while(!file1.eof())
  { file1 >> x;
    inc[i][j]=x;
    j++;
    if (j==gsize+1) { j=1; i++; }
  }
  file1.close();
  displayinc(); 
}

//------------------------//
// routines for the snake //
//------------------------//

void displaysnake()
{ // displays the snake on the screen in z columns //
  int i,j,k,x,y,z;
  
  z=4; x=(m/z)+1;
  for (i=m+1; i<=m+z; i++) { a[i]=0; c[i]=0; }  
  cout << "The snake." << endl;
  for (i=1; i<=x; i++)
  { cout << endl;
    for (k=1; k<=z; k++)
    { y=(k-1)*x;
      cout << setw(4) << a[i+y];
      cout << setw(4) << c[i+y];
      cout << setw(4) << d[a[i+y]];
      cout << "     ";
    }   
  }
  cout << endl;
  cout << "m=" << m << endl;
  cout << "Press 9 to continue" << endl;
  //cin >> x;  
}

void readsnake(string in_file_name)
{ // Reads the snake from the disc. //
  int i,x;
   
  file2.open(in_file_name.c_str(), ios::in); 
  i=0; 
  while(!file2.eof())
  { i++;
    file2 >> x; a[i]=x;
    file2 >> x; c[i]=x;
  }
  file2.close();
  m=i-1;
  for (i=1; i<=m; i++) { d[a[i]]=c[i]; }
  displaysnake();
} 


//---------------------//
// coloring with links //
//---------------------//

void order()
{ // orders the color multiplicities //
  // orders the color classes        //
  int i,j,z,y,x,t,max,r;
  
  t=0; z=csize-level; x=0;
  for (i=1; i<=z; i++) 
  { max=0; 
    for (j=1; j<=act; j++) 
    { if (max<mult[j]) { max=mult[j]; r=j; } }
    x=x+max;  y=addr[r];   
    for (j=1; j<=max; j++) 
    { prosp[level][++t]=a[y]; y=up[y]; }
    mult[r]=0;
  }
  bound[level]=x;
  for (j=1; j<=act; j++)
  { y=addr[j];
    for (i=1; i<=mult[j]; i++) 
    { prosp[level][++t]=a[y]; y=up[y]; } 
  }
}


void bogdan()
{ // greedy sequential coloring using buckets //
  // implemeted by means of pointers          //
  int i,j,x,y,u,v,pivot;
  int w,t;
  bool r,s;
  
  x=size[level]; act=0;
  for (u=1; u<=x; u++) 
  { j=1; r=1; pivot=a[u]; 
    while (j<=act) 
    { i=1; s=1; v=mult[j]; y=addr[j];
      while (i<=v) 
      { if (inc[pivot][a[y]]) { s=0; i=gsize; }
        i++; y=up[y];
      }
      if (s) { up[u]=addr[j]; addr[j]=u; mult[j]++; r=0; j=gsize; }
      j++;
    }
    if (r) { mult[++act]=1; addr[act]=u; up[u]=0; }
  }
  order();
}


//-------------------------//
// routines for the search //
//-------------------------//

void displayprosp()
{ // Displays the prospective nodes //
  // the size is gsize by gsize     //
  int i,j,x;
         
  cout << "The prospective matrix." << endl;
  for (i=1; i<=level; i++)
  { cout << endl;
    cout << setw(3) << bound[i];
    cout << setw(3) << size[i] << "--";
    for (j=1; j<=size[i]; j++)
    { cout << setw(3) << prosp[i][j]; }
  }
  cout << endl;
  cout << "Press 9 to continue" << endl;
  //cin >> x; 
}

void progress()
{ // Monitors the progress of the search. //
  // nnodes++; //
  step++; total++; tree[level]++;
  if ( step==10000000 ) 
  { nnodes++; step=0; 
    cout << endl;
    cout << setw(10) << nnodes;
    cout << setw(10) << nsol;
    cout << setw(10) << size[1]; 
  } 
}     

void dominance()
{ // Tests dominance. //
  int i,j,x,y,z,u,v;
  bool w;
  
  // if ( allsol==0 ) 
  { if ( 2<=level) 
    { x=level-1;
      y=size[x]-size[level];
      if ( y<=5 )
      { w=1;
        for (i=1; i<=y-2; i++)
        { u=prosp[x][gsize+1-i+1];
          for (j=i+1; j<=y-1; j++)
          { v=prosp[x][gsize+1-j+1];
            if ( inc[u][v]==1 ) { w=0; }
          }   
        }
        if ( w ) { bound[x]=size[x]-1; }
      }
    }     
  }
}

void solution()
{ // Handles the soltions. //
  nsol++; 
  if ( allsol==0 ) { level=0; }
}

void solution1()
{ // Displays solution on screen //
  int i,x;
  
  nsol++; 
  for(i=1; i<=csize; i++)
  { d[i]=prosp[i][size[i]]; }
  cout << "Solution" << endl;
  for (i=1; i<=csize; i++)
  { cout << setw(3) << d[i]; }
  cout << endl;
  cout << "Press 9 to continue" << endl;
  //cin >> x;
  
  if ( allsol==0 ) { level=0; }
}

void solution2()
{ // Saves solutions on the disc. //
  int i,x;
  
  nsol++; 
  for(i=1; i<=csize; i++)
  { d[i]=prosp[i][size[i]]; 
    file3 << d[i] << endl; }
  // file3 << endl;
  
  if ( allsol==0 ) { level=0; }
}


void test()
{ int i,t,x,y,z,s;

  x=size[level]; z=bound[level];
  // if (x<0) { x=0; }
  // if (z<0) { z=0; }
  while (x>z)
  { pivot=prosp[level][x]; t=0; s=gsize+2;
    for(i=1; i<=x-1; i++) 
    { y=prosp[level][i];
      if (inc[pivot][y]) { a[++t]=y; }
      else { s--; prosp[level+1][s]=y; }
      // if (inc[pivot][prosp[level][i]])
      // { a[++t]=prosp[level][i]; }
    }
    progress();
    size[++level]=t; x=t;
    bogdan(); 
    z=bound[level];
    // displayprosp(); //
    dominance();
    if (level==csize1) { solution2(); x=0; z=0; }       
  }
  size[level]=0;
  if (size[--level]>0) { size[level]--; }                
}

//----------------------------//
// setting the initial values //
//----------------------------//

void setting()
{ // setting the initial values // 
  int i,x;
  
  nnodes=0; nsol=0; step=0;
  x=0;
  for (i=1; i<=m; i++)
  { prosp[1][i]=a[m-i+1];
    if (c[i]<csize) { x++; } 
  }
  for(i=1;i<=csize+1;++i){
    size[i]=0; bound[i]=0;} 
  level=1;
  size[1]=m; 
  // displayprosp(); //
  // the following is a safety measure //
  size[0]=0;
  bound[1]=x;
  csize1=csize+1;
}

//--------------------------------//
// routines for generating repors //
//--------------------------------//

void displaytree()
{ // displays the search tree on the screen //
  int i,x;
  
  cout << endl;
  // if ( displ==1 ) 
  { for (i=1; i<=csize+1; i++) 
    { cout << setw(5) << i;
      cout << setw(12) << tree[i] << endl;
    }
  }
  cout << "nnodes=" << nnodes << endl;
  cout << "nsol=" << nsol << endl;
  cout << "total=" << total << endl;    
  cout << "Press 9 to continue" << endl;
  //cin >> x; 
}


/*int main(int argc, char **argv)
{ // Setting the initial values. //
  //===========================//
  gsize=512; csize=68; allsol=0;
  displ=0; savesol=0;
  //===========================//
  if(argv[1]==NULL){
    cout<<"usage: "<<endl<<argv[0]<<" IN_FILE"<<endl;
    return 1;
  } 
  string in_file_name(argv[1]);
  long double t0, t1;

  for(csize=100;csize>10;--csize){
    cout<<endl<<"**********************"<<endl;
    cout<<"csize = "<<csize<<endl<<"**********************"<<endl<<endl;
    readinc(in_file_name+".dat");
    readsnake(in_file_name+"-cbr.snake");
    setting();
    

    // main loop //
    // opens the file for the solutions //
    if (savesol==1) 
      { file3.open("d:\\cprog\\sollist.dat", ios::out | ios::trunc); }
    
    t0=clock();
    while( level>0 )
      { test(); 
	// displayprosp(); //
      }
    // closes the file for the solutions //
    if (savesol==1) 
      { file3.close(); }      
    
    displaytree();
    cout<<"csize = "<<csize<<endl;
    t1=clock();
    cout<<"time : "<<((t1-t0)/CLOCKS_PER_SEC)<<" sec"<<endl;
    //exit if no more solutions!
    if(nsol>=1) exit(0);
  }
}
*/

